package algo.tree;


import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;

public class RedBlackTree<T extends Comparable<? super T>>{

    protected int N;
    protected RBTreeNode<T> head;
    protected RBTreeNode<T> root;

    protected static final boolean COLOR_BLACK = true;
    protected static final boolean COLOR_RED = false;

    protected static final boolean BLACK = true;
    protected static final boolean RED = false;
    public RedBlackTree() {
        N = 0;
        head = new RBTreeNode<>();
        root = null;
    }

    public void printPreTraverse() {
        System.out.println("\nPreOrder Traverse:");
        RBTreeNode<T> node = root;
        printPreTraverseRecurrence(node);
        System.out.println();
    }
    protected void printPreTraverseRecurrence(RBTreeNode<T> node) {
        if (node == null) return;

        printPreTraverseRecurrence(node.left);
        System.out.print(node.val + " ");
        printPreTraverseRecurrence(node.right);
    }
    public void printMidTraverse() {
        System.out.println("\nMidOrder Traverse:");
        RBTreeNode<T> node = root;
        printMidTraverseRecurrence(node);
        System.out.println();
    }
    protected void printMidTraverseRecurrence(RBTreeNode<T> node) {
        if (node == null) return;

        System.out.print(node.val + " ");
        printMidTraverseRecurrence(node.left);
        printMidTraverseRecurrence(node.right);
    }
    public void printPostTraverse() {
        System.out.println("\nPostOrder Traverse:");
        RBTreeNode<T> node = root;
        printPostTraverseRecurrence(node);
        System.out.println();
    }
    protected void printPostTraverseRecurrence(RBTreeNode<T> node) {
        if (node == null) return;

        printPostTraverseRecurrence(node.left);
        printPostTraverseRecurrence(node.right);
        System.out.print(node.val + " ");
    }
    public void printLevelTraverse() {
        System.out.println("\nLevel Traverse:");
        if (root == null) return;

        RBTreeNode<T> node = root;
        Queue<RBTreeNode<T>> queue = new LinkedList<>();
        queue.add(node);

        while (queue.size() > 0) {
            int size = queue.size();

            while (size-- > 0) {
                node = queue.poll();
                if (node == root) System.out.print(node.val + " ");
                else System.out.print(node.parent.val
                        +"."+(node==node.parent.left?"left=":"right=")
                        +node.val+"\t");
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            System.out.println();
        }
    }


    protected RBTreeNode<T> lastAccess = null;
    public boolean contains(T value) {
        if (lastAccess != null && equalTo(value, lastAccess.val)) {
            return true;
        }
        RBTreeNode<T> node = root;
        while (node != null) {
            int cmp = compare(value, root.val);

            if (cmp < 0)        node = node.left;
            else if (cmp > 0)   node = node.right;
            else                {
                lastAccess = node;
                return  true;
            }
        }
        return false;
    }
    public T search(T value) {
        if (lastAccess != null && equalTo(value, lastAccess.val)) {
            return lastAccess.val;
        }
        RBTreeNode<T> node = root;
        while (node != null) {
            int cmp = compare(value, root.val);

            if (cmp < 0)        node = node.left;
            else if (cmp > 0)   node = node.right;
            else                {
                lastAccess = node;
                return  node.val;
            }
        }
        return null;
    }
/*
    public boolean insert(T value) {
        // 1. 按照二叉搜索树的规则插入新节点
        // 空树
        if (root == null) {
            root = new RBTreeNode<>(head, value, COLOR_BLACK);
            head.parent = root;
            ++N;
        } else {
            // 非空
            // 按照二叉搜索树的特性找待插入节点在树中的位置
            RBTreeNode<T> node = root;
            RBTreeNode<T> parent;
            int cmp;

            do {
                parent = node;
                cmp = compare(value, node.val);

                if (cmp < 0)        node = node.left;
                else if (cmp > 0)   node = node.right;
                else                return false;
            } while (node != null);

            // 插入新节点
            node = new RBTreeNode<>(parent, value);
            if (cmp < 0)    parent.left = node;
            else            parent.right = node;

            ++N;
            // 2. 检测新节点插入之后是否违反性质三：即是否存在红色节点连在一起的情况
            //    因为新插入节点cur的颜色是红色的，如果cur双亲parent节点的颜色也是红色的
            //    则违反了性质三
            while (isRed(parent)) {
                // 违反了性质三
                RBTreeNode<T> grandParent = parent.parent;

                // 此处grandFather一定不为空
                // 因为：parent是红色的，则parent一定不是根节点，parent的双亲一定是存在的
                if (parent == grandParent.left) {
                    // 三种情况
                    RBTreeNode<T> uncle = grandParent.right;
                    if (uncle != null && isRed(uncle)) {
                        // 情况一：叔叔节点存在且为红
                        parent.color = COLOR_BLACK;
                        uncle.color = COLOR_BLACK;
                        grandParent.color = COLOR_RED;
                        node = grandParent;
                        parent = node.parent;
                    } else {
                        // 叔叔节点为空 || 叔叔节点存在且为黑--->即情况二 或者 情况三
                        // 情况三
                        if (node == parent.right) {
                            // 先对parent进行左单旋，然后将parent和cur交换---->变成情况二
                            rotateLeft(parent);
                            swap(parent, node);
                        }

                        // 情况二：
                        // 将祖父和双亲节点的颜色交换，然后再对祖父树进行右单旋
                        grandParent.color = COLOR_RED;
                        parent.color = COLOR_BLACK;
                        rotateRight(grandParent);
                    }
                } else {
                    // 三种情况
                    RBTreeNode<T> uncle = grandParent.left;
                    if (uncle != null && isRed(uncle)) {
                        // 情况一：叔叔节点存在且为红
                        parent.color = COLOR_BLACK;
                        uncle.color = COLOR_BLACK;
                        grandParent.color = COLOR_RED;
                        node = grandParent;
                        parent = node.parent;
                    } else {
                        // 叔叔节点为空 || 叔叔节点存在且为黑--->即情况二 或者 情况三
                        // 情况三
                        if (node == parent.left) {
                            // 先对parent进行右单旋，然后将parent和node交换---->变成情况二
                            rotateRight(parent);
                            swap(parent, node);
                        }

                        // 情况二：
                        // 将祖父和双亲节点的颜色交换，然后再对祖父树进行左单旋
                        grandParent.color = COLOR_RED;
                        parent.color = COLOR_BLACK;
                        rotateLeft(grandParent);
                    }
                }
            }
        }

        head.left = getMostLeft();
        head.right = getMostRight();
        root.color = COLOR_BLACK;
        return true;
    }
*/
    public boolean insert(T value) {
        // 1. 按照二叉搜索树的规则插入新节点
        // 空树
        if (root == null) {
            root = new RBTreeNode<>(head, value, COLOR_BLACK);
            head.parent = root;
            ++N;
        } else {
            // 非空
            // 按照二叉搜索树的特性找待插入节点在树中的位置
            RBTreeNode<T> node = root;
            RBTreeNode<T> parent;
            int cmp;

            do {
                parent = node;
                cmp = compare(value, node.val);

                if (cmp < 0)        node = node.left;
                else if (cmp > 0)   node = node.right;
                else                return false;
            } while (node != null);

            // 插入新节点
            node = new RBTreeNode<>(parent, value);
            if (cmp < 0)    parent.left = node;
            else            parent.right = node;

            ++N;
            lastAccess = node;
            // 2. 检测新节点插入之后是否违反性质三：即是否存在红色节点连在一起的情况
            //    因为新插入节点cur的颜色是红色的，如果cur双亲parent节点的颜色也是红色的
            //    则违反了性质三
            if (isRed(parent))
                fixAfterInsertion2(node);
        }

        head.left = getMostLeft();
        head.right = getMostRight();
        root.color = COLOR_BLACK;
        return true;
    }
    protected void fixAfterInsertion2(RBTreeNode<T> node) {
        do {
            RBTreeNode<T> uncle;
            if (node.parent == node.parent.parent.left) {
                uncle = node.parent.parent.right;
                if (isRed(uncle)) {
                    paintRed(node.parent.parent);
                    paintBlack(node.parent);
                    paintBlack(uncle);
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);
                    }

                    paintBlack(node.parent);
                    paintRed(node.parent.parent);
                    rotateRight(node.parent.parent);
                }
            } else {
                uncle = node.parent.parent.left;
                if (isRed(uncle)) {
                    paintRed(node.parent.parent);
                    paintBlack(node.parent);
                    paintBlack(uncle);
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.left) {
                        node = node.parent;
                        rotateRight(node);
                    }

                    paintBlack(node.parent);
                    paintRed(node.parent.parent);
                    rotateLeft(node.parent.parent);
                }
            }

        } while (isRed(node.parent));
    }
    public boolean delete(T value) {
        RBTreeNode<T> node;
        if (lastAccess != null && equalTo(value, lastAccess.val)) {
            node = lastAccess;
            lastAccess = null;
        } else {
            node = root;
            while (node != null) {
                int cmp = compare(value, node.val);
                if (cmp < 0)        node = node.left;
                else if (cmp > 0)   node = node.right;
                else                break;
            }
        }

        if (node == null) return false;
//        if (node == node.parent.left) {
//            fixAfterDeletion(deleteNode(node), true);
//        } else {
//            fixAfterDeletion(deleteNode(node), false);
//        }
        deleteNode(node);
        return true;
    }
    protected void deleteNode(RBTreeNode<T> node) {
        --N;
        // 待删除结点是有两个子结点的内部结点
        if (node.left != null && node.right != null) {
            // 与后继结点替换
            RBTreeNode<T> successorNode = getSuccessor(node);
            node.val = successorNode.val;
            // 开始删除该后继结点
            node = successorNode;
        }

        // 到这里，node 所指向的结点只可能有 1 个或 0 个子结点 ?
        RBTreeNode<T> replacement = node.left != null ? node.left : node.right;

        if (replacement != null) { // 替换结点不为空，即 p 有一个子结点
            replacement.parent = node.parent; // 用替换结点替换 p
            if (node.parent == head)    // p 为根结点
                root = replacement;
            else if (node == node.parent.left)
                node.parent.left = replacement;
            else
                node.parent.right = replacement;
            node.left = node.right = node.parent = null;

            if (node.color == COLOR_BLACK) // 若被删除的结点为黑色结点，执行自平衡修复
                fixAfterDeletion(replacement);
        } else if (node.parent == head) {// p 为叶子结点，且 p 为根结点，即此时红黑树只有一个结点
            root = null;
        } else {    // p 为叶子结点
            if (node.color == COLOR_BLACK) // 若被删除的结点为黑色结点，执行自平衡修复
                fixAfterDeletion(node);

//            if (node.parent != head) {
            if (node.parent != null) {
                if (node == node.parent.left)
                    node.parent.left = null;
                else if (node == node.parent.right)
                    node.parent.right = null;

                node.parent = null;
            }
        }
    }
    protected RBTreeNode<T> getSuccessor(RBTreeNode<T> t) {
        if (t == null)
            return null;
        else if (t.right != null) {
            RBTreeNode<T> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            RBTreeNode<T> p = t.parent;
            RBTreeNode<T> ch = t;
//            while (p != null && ch == p.right) {
            while (p != head && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }
    protected RBTreeNode<T> leftOf(RBTreeNode<T> node) {
        return node == null ? null : node.left;
    }
    protected RBTreeNode<T> rightOf(RBTreeNode<T> node) {
        return node == null ? null : node.right;
    }

    protected boolean colorOf(RBTreeNode<T> node) {
        return isBlack(node);
    }
    protected void setColor(RBTreeNode<T> node, boolean color) {
        if (node != null)
            node.color = color;
    }
    protected void fixAfterDeletion(RBTreeNode<T> node) {
        while (node != root && colorOf(node) == BLACK) {
            if (node == leftOf(parentOf(node))) {
                RBTreeNode<T> sib = rightOf(parentOf(node));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(node), RED);
                    rotateLeft(parentOf(node));
                    sib = rightOf(parentOf(node));
                }

                if (colorOf(leftOf(sib))  == BLACK &&
                        colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    node = parentOf(node);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(node));
                    }
                    setColor(sib, colorOf(parentOf(node)));
                    setColor(parentOf(node), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(node));
                    node = root;
                }
            } else { // symmetric
                RBTreeNode<T> sib = leftOf(parentOf(node));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(node), RED);
                    rotateRight(parentOf(node));
                    sib = leftOf(parentOf(node));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                        colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    node = parentOf(node);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(node));
                    }
                    setColor(sib, colorOf(parentOf(node)));
                    setColor(parentOf(node), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(node));
                    node = root;
                }
            }
        }

        setColor(node, BLACK);
    }
    protected void fixAfterDeletion2(RBTreeNode<T> node) {
        RBTreeNode<T> parent = node.parent;
//        while (node != root && isRed(node)) { // 当 n 为根结点或红色结点时结束循环
        while (node != root && node.color == COLOR_RED) { // 当 n 为根结点或红色结点时结束循环
            RBTreeNode<T> successor = parent.right;
            RBTreeNode<T> successorLeft;
            RBTreeNode<T> successorRight;
            if (successor == null) {
                successorLeft = null;
                successorRight = null;
            } else {
                successorLeft = successor.left;
                successorRight = successor.right;
            }

            if (node == parent.left) {
                if (successor.color == COLOR_RED) {  // 进入情形 1
                    paintBlack(successor);
                    paintRed(parent);
                    rotateLeft(parent);
                    successor = parent.right;
                    if (successor == null) {
                        successorLeft = null;
                        successorRight = null;
                    } else {
                        successorLeft = successor.left;
                        successorRight = successor.right;
                    }
                }
//                if (successorLeft.color == COLOR_BLACK &&
                if (isBlack(successorLeft) &&
                    isBlack(successorRight)) { // 进入情形 2
//                    successorRight.color == COLOR_BLACK) { // 进入情形 2
                    paintRed(successor);       // 兄弟结点置为红色
                    node = parent;                   // 继续从父结点开始向上修复
                } else {
                    if (successorRight.color == COLOR_BLACK) { // 进入情形 3，以 S 进行左旋转
                        paintBlack(successorLeft);
                        paintRed(successor);
                        rotateRight(successor);
                        successor = parent.right;
                        successorLeft = successor.left;
                        successorRight = successor.right;
                    }
                    successor.color = parent.color;  // 进入情形 4，以 P 进行右旋转，结束修复
                    paintBlack(parent);
                    paintBlack(successorRight);
                    rotateLeft(parent);
                    node = root;  // 结束循环
                }
            } else {
//                if (successor.color == COLOR_RED) {  // 进入情形 1
                if (isRed(successor)) {  // 进入情形 1
                    paintBlack(successor);
                    paintRed(parent);
                    rotateRight(parent);
                    successor = parent.left;
//                    successorLeft = successor.left;
//                    successorRight = successor.right;
                    if (successor == null) {
                        successorLeft = null;
                        successorRight = null;
                    } else {
                        successorLeft = successor.left;
                        successorRight = successor.right;
                    }
                }
//                if (successorLeft.color == COLOR_BLACK &&
                if (isBlack(successorLeft) &&
                    isBlack(successorRight)) { // 进入情形 2
//                        successorRight.color == COLOR_BLACK) { // 进入情形 2
                    paintRed(successor);       // 兄弟结点置为红色
                    node = parent;                   // 继续从父结点开始向上修复
                } else {
                    if (successorRight.color == COLOR_BLACK) { // 进入情形 3，以 S 进行左旋转
                        paintBlack(successorLeft);
                        paintRed(successor);
                        rotateLeft(successor);
                        successor = parent.left;
                        successorLeft = successor.left;
                        successorRight = successor.right;
                    }
                    successor.color = parent.color;  // 进入情形 4，以 P 进行右旋转，结束修复
                    paintBlack(parent);
                    paintBlack(successorLeft);
                    rotateRight(parent);
                    node = root;  // 结束循环
                }
            }
        }
        paintBlack(node); // 对于上面提到的第二种情形，红色子结点会在这里被置为黑色
    }
    protected void fixAfterInsertion(RBTreeNode<T> node) {
        while (isRed(node.parent)) {
            RBTreeNode<T> uncle;
            if (parentOf(node) == parentOf(parentOf(node)).left) {
                uncle = parentOf(parentOf(node)).right;
                if (isRed(uncle)) {
                    parentOf(node).color = COLOR_BLACK;
                    uncle.color = COLOR_BLACK;
                    parentOf(parentOf(node)).color = COLOR_RED;
                    node = parentOf(parentOf(node));
                } else {
                    if (node == parentOf(node).right) {
                        node = parentOf(node);
                        rotateLeft(node);
                    }

                    parentOf(node).color = COLOR_BLACK;
                    parentOf(parentOf(node)).color = COLOR_RED;
                    rotateRight(parentOf(parentOf(node)));
                }
            } else {
                uncle = parentOf(node).left;
                if (isRed(uncle)) {
                    parentOf(node).color = COLOR_BLACK;
                    uncle.color = COLOR_BLACK;
                    parentOf(parentOf(node)).color = COLOR_RED;
                    node = parentOf(parentOf(node));
                } else {
                    if (node == parentOf(node).left) {
                        node = parentOf(node);
                        rotateRight(node);
                    }

                    parentOf(node).color = COLOR_BLACK;
                    parentOf(parentOf(node)).color = COLOR_RED;
                    rotateLeft(parentOf(parentOf(node)));
                }
            }
        }
    }
    protected RBTreeNode<T> parentOf(RBTreeNode<T> node) {
        return (node == null || node == head)? null : node.parent;
    }
    protected void rotateLeft0(RBTreeNode<T> node) {
        if (node != null) {
            RBTreeNode<T> r = node.right;
            node.right = r.left;
            if (r.left != null)
                r.left.parent = node;
            r.parent = node.parent;
            if (node.parent == null)
                root = r;
            else if (node.parent.left == node)
                node.parent.left = r;
            else
                node.parent.right = r;
            r.left = node;
            node.parent = r;
        }
    }
    protected void rotateRight0(RBTreeNode<T> node) {
        if (node != null) {
            RBTreeNode<T> l = node.left;
            node.left = l.right;
            if (l.right != null) l.right.parent = node;
            l.parent = node.parent;
            if (node.parent == null)
                root = l;
            else if (node.parent.right == node)
                node.parent.right = l;
            else node.parent.left = l;
            l.right = node;
            node.parent = l;
        }
    }
    protected void rotateLeft(RBTreeNode<T> node) {
        if (node != null) {
            RBTreeNode<T> rightChild = node.right;
            node.right = rightChild.left;
            if (rightChild.left != null)
                rightChild.left.parent = node;

            rightChild.parent = node.parent;
            if (node.parent == head) {
                head.parent = rightChild;
                root = rightChild;
            } else if (node.parent.left == node) {
                node.parent.left = rightChild;
            } else {
                node.parent.right = rightChild;
            }
            rightChild.left = node;
            node.parent = rightChild;
        }
    }

    protected void rotateRight(RBTreeNode<T> node) {
        if (node != null) {
            RBTreeNode<T> leftChild = node.left;
            node.left = leftChild.right;
            if (leftChild.right != null)
                leftChild.right.parent = node;

            leftChild.parent = node.parent;
            if (node.parent == head) {
                head.parent = leftChild;
                root = leftChild;
            } else if (node.parent.left == node) {
                node.parent.left = leftChild;
            } else {
                node.parent.right = leftChild;
            }
            leftChild.right = node;
            node.parent = leftChild;
        }
    }

/*
    protected void swap(RBTreeNode<T> a, RBTreeNode<T> b) {
    // 颜色也需要交换吗？
        T tmp = a.val;
        a.val = b.val;
        b.val = tmp;
    }
*/

    protected RBTreeNode<T> getMostLeft() {
        RBTreeNode<T> node = root;
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    protected RBTreeNode<T> getMostRight() {
        RBTreeNode<T> node = root;
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    class RBTreeNode<T> {
        public boolean color;
        public T val;
        public RBTreeNode<T> left;
        public RBTreeNode<T> right;
        public RBTreeNode<T> parent;

        RBTreeNode() {
            color = COLOR_BLACK;
        }
        RBTreeNode(RBTreeNode parent, T value) {
            this.val = value;
            this.parent = parent;
            color = COLOR_RED;
        }
        RBTreeNode(RBTreeNode parent, T value, boolean color) {
            this.val = value;
            this.parent = parent;
            this.color = color;
        }
    }
    protected boolean less(T a, T b) {
        return a.compareTo(b) < 0;
    }
    protected boolean greater(T a, T b) {
        return a.compareTo(b) > 0;
    }

    protected int compare(T a, T b) {
        return a.compareTo(b);
    }
    protected boolean equalTo(T a, T b) {
        return a.compareTo(b) == 0;
    }

    protected boolean isBlack(RBTreeNode<T> node) {
//        return !isRed(node);
        return node == null || node.color;
    }

    protected void paintBlack(RBTreeNode<T> node) {
        if (node != null) node.color = COLOR_BLACK;
    }
    protected void paintRed(RBTreeNode<T> node) {
        if (node != null) node.color = COLOR_RED;
    }


    protected boolean isRed(RBTreeNode<T> node) {
        return node != null && !node.color;
    }
}
